package qujian;

import java.util.Arrays;

/**
 * 354. 俄罗斯套娃信封问题
 * 给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
 *
 * 当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
 *
 * 请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
 *
 * 注意：不允许旋转信封。
 *
 *
 * 示例 1：
 *
 * 输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
 * 输出：3
 * 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
 *
 * @author luolidong
 * @version 1.0
 * @create 2021-08-03 20:28
 */
public class L354 {
    public int maxEnvelopes(int[][] envelopes) {
        Arrays.sort(envelopes, (x, y) -> x[0] != y[0] ? x[0] - y[0] : y[1] - x[1]);
        int[] dp=new int[envelopes.length];
        int max=1;
        Arrays.fill(dp, 1);
        for (int i = 1; i <envelopes.length ; i++) {
            for (int j = 0; j <i ; j++) {
                //前提，第二位降序排列，如：[[1,4],[1,2],[2,5],[3,5]]
                //如此只需比较第二位
                if(envelopes[i][1]>envelopes[j][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            max=Math.max(max,dp[i]);
        }
        return max;
    }
}
